package leetcode_81_100;

import java.util.ArrayList;
import java.util.List;

public class grayCode_89 {
    /**
     * 给你一个整数 n ，返回任一有效的 n 位格雷码序列 。
     * n 位格雷码序列参考leetcode
     * @param n
     * @return
     */
    public List<Integer> grayCode(int n) {
        /**
         * 示例
         * [0,1,3,2] 的二进制表示是 [00,01,11,10] 。
         * - 00 和 01 有一位不同
         * - 01 和 11 有一位不同
         * - 11 和 10 有一位不同
         * - 10 和 00 有一位不同
         *
         * 因为第一个整数是 0，所以这n位二进制能表示的十进制数字
         * 必然是0  ~ 2^n (位操作表示即为1<< n ) - 1的组合
         * 例如3位格雷编码，表示范围   000~111（0~7）
         *
         * 思路是直接查，格雷编码的生成过程, G(i) = i ^ (i/2);
         */
        List<Integer> res = new ArrayList<>();
        if (n < 0) return res;

        //<< 按位左移运算符。左操作数按位左移右操作数指定的位数。
        //>> 按位右移运算符。左操作数按位右移右操作数指定的位数。
        for (int i = 0; i < 1 << n; i++) { //n=3时，即 0001左移三位  1000        000<=i<=111
            res.add(i ^ i >> 1);       // >> 优先级高于 ^
            // ^如果相对应位值相同，则结果为0，否则为1
            // 100  >>1  -> 010        010^100  -> 110
            // 101  >>1  -> 010        010^101  -> 111
        }
        return res;
    }
}
